﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode.CodeDay
{
    public partial class Code
    {
        /**
         * 冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
        在加热器的加热半径范围内的每个房屋都可以获得供暖。
        现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
        说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
        示例 1:
        输入: houses = [1,2,3], heaters = [2]
        输出: 1
        解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖
         */
        public int FindRadius(int[] houses, int[] heaters)
        {
            int minH = houses[0];
            int maxH = houses[0];
            for (int i = 1; i < houses.Length; i++)
            {
                if (minH >= houses[i])
                    minH = houses[i];
                if (maxH <= houses[i])
                    maxH = houses[i];
            }

            int minM = heaters[0];
            int maxM = heaters[0];
            for (int i = 1; i < heaters.Length; i++)
            {
                if (minM >= heaters[i])
                    minM = heaters[i];
                if (maxM <= heaters[i])
                    maxM = heaters[i];
            }
            int maxR = Math.Abs(minM - maxH);
            if (Math.Abs(minM - minH) > maxR)
                maxR = Math.Abs(minM - minH);
            int leftR = 0;
            int rightR = maxR;
            while (leftR != rightR && leftR + 1 != rightR)
            {
                if (ContainsAll(houses, heaters, (leftR + rightR) / 2))
                    rightR = (leftR + rightR) / 2;
                else
                    leftR = (leftR + rightR) / 2;
            }

            if (ContainsAll(houses, heaters, leftR))
                return leftR;
            if (ContainsAll(houses, heaters, rightR))
                return rightR;
            return 0;
        }

        public bool ContainsAll(int[] houses, int[] heaters, int RS)
        {
            foreach (var houseItem in houses)
            {
                bool isExists = false;
                foreach (var heaterItem in heaters)
                {
                    if ((heaterItem - RS) <= houseItem && (heaterItem + RS) >= houseItem)
                    {
                        isExists = true;
                        break;
                    }
                }
                if (isExists == false)
                    return false;
            }
            return true;
        }
    }
}